package demo.DataStrucAndAlgo.Tree.BinarySortTree;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/8/6-08-06-13:54
 * @Description：demo.DataStrucAndAlgo.Tree     二叉排序树
 */
/*
BST树-二叉排序树
    满足左子节点小于父节点，右子节点大于父节点的树（若有等于情况，添加至右子节点）
 */
class Node{
    private int data;
    private Node left;
    private Node right;

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    /**
     *   符合BST树建立规则，左子树小于父节点，右节点大于父节点
     * @param newNode  要添加的结点
     */
    public void add(Node newNode){
        if(newNode.data < this.data){       //小数据往左边放
            if(this.getLeft() == null){
                this.setLeft(newNode);
            }else{
                this.getLeft().add(newNode);
            }
        }else{            //大数据往右子树走
            if(this.getRight() == null){
                this.setRight(newNode);
            }else{
                this.getRight().add(newNode);
            }
        }
    }

    /**
     * 按照输入的value，查找拥有相同值的结点
     * @param value   匹配的值
     * @return    找到返回结点，否则返回空
     */
    public Node search(int value){
        if(this.getData() == value){
            return this;
        }else if(value < this.getData()){
            if(this.getLeft() == null){
                return null;
            }else{
                return this.getLeft().search(value);
            }
        }else{
            if(this.getRight() == null){
                return null;
            }else{
                return this.getRight().search(value);
            }
        }
    }

    /**
     * 按照输入的value，查找拥有相同值的结点
     * @param value   匹配的值
     * @return   找到返回结点，否则返回空
     */
    public Node searchParent(int value){
        if((this.getLeft() != null && this.getLeft().getData() == value) || (this.getRight() != null && this.getRight().getData() == value)){
            return this;
        }
        if(this.getLeft()!= null && value< this.getLeft().getData()){
            return this.getLeft().searchParent(value);
        } else if(this.getRight() != null && value > this.getRight().getData()){
            return this.getRight().searchParent(value);
        }else{
            return null;
        }
    }

    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.print(this + " ");
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
    public void cengciOrder(Queue<Node> queue){
        if(!queue.isEmpty()){
            Node node = queue.poll();
            System.out.print(node + " ");
            if(node.getLeft() != null){
                queue.add(node.getLeft());
            }
            if(node.getRight()!= null){
                queue.add(node.getRight());
            }
            node.cengciOrder(queue);
        }
    }
    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }

    public Node(int data) {
        this.data = data;
    }

}
class binarySTree{
    private Node root;

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }
    public void add(Node node){
        if (node==null){
            System.out.println("结点为空");
            return;
        }
        if (this.root==null){
            this.root=node;
        }else{
            this.root.add(node);
        }
    }
    public void infixOrder(){
        if (this.root==null){
            System.out.println("根节点为空");
            return;
        }
        this.root.infixOrder();
        System.out.println();
    }
    public void cengciOrder(){
        if(this.root==null){
            System.out.println("根节点为空");
            return;
        }
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(this.root);
        this.root.cengciOrder(queue);
        System.out.println();
    }
    public Node search(int value){
        if (root==null){
            System.out.println("空树");
            return null;
        }
        return this.root.search(value);
    }
    public Node searchParent(int value){
        if (this.root==null){
            System.out.println("空树");
            return null;
        }
        return this.root.searchParent(value);
    }

    /*
    删除结点有多种情况：
        1，树中只有一个结点：root置空
        2，删除叶子结点：父节点对左或右子节点置空
        3，删除含有左右子树的节点：利用delRightMin方法找到节点右子树中的最小值结点，将其删除，并将其值覆盖到节点中
        4，删除只含有一个子树的结点：父节点对其重新设置为该节点的对应非空子节点
     */
    public void delete(int value){
        if(this.root == null){
            throw new RuntimeException("空树");
        }
        if(this.root.getData() == value){
            Node node = findRightMin(root);
            node.setLeft(root.getLeft());
            node.setRight(root.getRight());
            root = node;
            return;
        }
        Node node = this.root.search(value);
        if(node == null){
            throw new RuntimeException("你要删除的结点不存在");
        }
        Node parent = this.root.searchParent(value);

        System.out.println(parent);
        System.out.println(node);
        if(node.getLeft() == null){     //要删除的结点左子树为空
            if(parent.getLeft() == node){      //该结点为父节点的左孩子
                parent.setLeft(node.getRight());
            }else{
                parent.setRight(node.getRight());
            }
        }else if(node.getRight() == null){    //要删除的结点右子树为空
            if(parent.getLeft() == node){      //该结点为父节点的左孩子
                parent.setLeft(node.getLeft());
            }else{
                parent.setRight(node.getLeft());
            }
        }else{         //要删除的结点左右子树都不为空
            Node temp = findRightMin(node);
            temp.setLeft(node.getLeft());
            temp.setRight(node.getRight());
            if(parent.getLeft() == node){      //该结点为父节点的左孩子
                parent.setLeft(temp);
            }else{
                parent.setRight(temp);
            }
        }
    }
    public Node findRightMin(Node node){
        Node temp = node.getRight();      //从要删除的右子树中找到最小的树作为新节点
        Node temp2 = node;
        while(temp.getLeft() != null){
            temp2 = temp;
            temp = temp.getLeft();
        }
        if(temp2.getRight() == temp){
            temp2.setRight(null);
        }else{
            temp2.setLeft(null);    //将找出的新节点从当前位置删除
        }
        return temp;
    }
}
public class BinarySortTree {
    public static void main(String[] args) {
        binarySTree tree = new binarySTree();
        tree.add(new Node(7));
        tree.add(new Node(3));
        tree.add(new Node(10));
        tree.add(new Node(12));
        tree.add(new Node(5));
        tree.add(new Node(1));
        tree.add(new Node(9));
        tree.add(new Node(0));

        tree.infixOrder();

        tree.delete(7);

        tree.infixOrder();
        System.out.println(" -------------------------");
        tree.cengciOrder();
    }
}
